/*
 * Maximum Path Sum II Solution.
 */

import Graph.*;
import Graph.AdjacencyListGraph.VertexIterator;
import Graph.AdjacencyListGraph.EdgeIterator;
import Graph.WeightedAdjacencyListGraph.WeightedEdge;
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Scanner;
import java.util.ArrayList;

/**
 * Implements a solution to the <a href="http://projecteuler.net/problem=67">
 * Maximum Path Sum II</a> problem on <a href="http://projecteuler.net/">
 * ProjectEuler.net</a>. 
 * <br />
 * 
 * This approach works by building a weighted direct graph using contents of the
 * input file as the weights.  The graph is processed by a "single source 
 * longest path" algorithm (a modification of Dijkstra's SSSP algorithm) that
 * calculates the longest path (in other words, largest sum) to each vertex in
 * the graph.  Finally, the longest path (largest sum) is selected and returned
 * as the solution to <a href="http://projecteuler.net/problem=67">
 * Maximum Path Sum II</a>.
 * 
 * This implementation is more than what is really required to solve 
 * <a href="http://projecteuler.net/problem=67"> Maximum Path Sum II</a>.
 * However, this implementation efficiently solves the 
 * <a href="http://projecteuler.net/problem=67"> Maximum Path Sum II</a> problem
 * while providing a foundation to solve other problems related to the 
 * numbers triangle.
 * 
 * 
 * @author Michael Silva
 */

public class Euler67Graph {
    
    /** Weighted directed graph. */
    private static WeightedAdjacencyListGraph graph = null;
    
    /** List of weights used when building the graph. */
    private static ArrayList<Integer> weights = null;
    
    /** Number of vertices in the graph. */
    private static int vCount = 0;
    
    /** Calculated "height" of the graph. */
    private static int height = 0;
    
    /** Tracks the maximum sums. */
    private static int [] sum = null;
    
    /** Tracks predecessors. */
    private static int [] pred = null;
    
    
    /**
     * Solves <a href="http://projecteuler.net/problem=67"> Maximum Path Sum II
     * </a> using a weighted direct graph data structure.
     *
     * @param fname Filename containing the number triangle
     * @return The largest possible sum
     */
    public static int solve(String fname)
    {
        buildGraph(fname);
        singleSourceLongestPath();
        return sum[ findLargestSum() ];        
    }
   
   
    /**
     * Resets static fields so <code>Euler67Graph.solve()</code> can be run 
	 * again.  This method must be called between each call to <code>solve()
	 * </code>.
     */
    public static void reset()
    {
        graph = null;
        weights = null;
        vCount = 0;
        height = 0;
        sum = null;
        pred = null;
    }
    
    
    /**
     * Builds a weighted directed graph using the contents of the input file
     * as weights.
     * 
     * @param fname Path to file containing a number triangle.
     */
    private static void buildGraph(String fname) 
    {
        buildWeightsList(fname);
        graph = new WeightedAdjacencyListGraph(vCount);
        addVertices();
        addEdges();
    }
    
    
    /**
     * Reads the file containing a number triangle, and uses the values to 
     * create a list of weights.
     * 
     * @param fname Path to file containing the number triangle.
     */
    private static void buildWeightsList(String fname)
    {
        // Initialize the weights list
        weights = new ArrayList<Integer>();
        
        // Try opening the input file
        BufferedReader bReader = null;
        try {
            bReader = new BufferedReader( new FileReader(fname) );
        } catch (IOException e) { }
        
        // Read the input file
        Scanner scanf = new Scanner(bReader);
        while(scanf.hasNext())
        {
            // Read a line of input
            String [] nums = scanf.nextLine().split(" ");
            height++;
            
            // Process each number
            for (int i=0; i < nums.length; i++){
               
                vCount++;
                
                // First or last entry on the line?
                if (i == 0 || i == nums.length-1) {
                    weights.add( new Integer(nums[i]) );
                }
                // All other values are used twice. Once as a "left child"
                // and once as a "right child"
                else {
                    weights.add( new Integer(nums[i]) );
                    weights.add( new Integer(nums[i]) );
                }
            }
        }
        
        // Close the input file
        try {
            if (bReader != null)    {
                bReader.close();    }
        } catch (IOException e) {}
    }
       
    
    /**
     * Adds vertices to the graph.  Each <code>Vertex</code> is given a
     * unique, sequential identifier beginning at 0.
     */
    private static void addVertices()
    {
        for (int i=0; i < vCount; i++){
            graph.addVertex( new Vertex(i, "") );
        }
    }
    
    
    /**
     * Completes the graph by adding weighted edges between vertices.  Edge
     * weights are taken sequentially from the <code>Euler67Graph.weights</code> 
     * <code>ArrayList</code>.
     */
    private static void addEdges()
    {
        // Tracks depth from the source.
        int depth = 1;
        
        // Used to moves through the weights list.
        int wIndex = 1;
        
        // Tracks how many vertices have been processed at the curernt depth.
        int dIndex = 0;
        
        // Index of the vertex currently being processed ("parent").
        int pIndex = 0;
        
        // Attach incident edges
        // The structure of the problem tells that each vertex, except those
        // at the greatest depth, will have exactly two incident edges.
        for ( ; depth < height; pIndex++)
        {
            // Add the left "child"
            int lIndex = (pIndex + 1) + (depth - 1);
            graph.addEdge(pIndex, lIndex, weights.get(wIndex++));
            
            // Add the right "child"
            int rIndex = (pIndex + 1) + (depth);
            graph.addEdge(pIndex, rIndex, weights.get(wIndex++));
            
            // Have all the vertices at the current depth been processed?
            // The problems tells that the number of vertices at each depth
            // matches the depth.
            if (++dIndex >= depth) {
                dIndex = 0;
                depth++;
            }
        }
    }
        

    /**
     * Applies a modification of Dijkstra's Single Source Shortest Path 
     * algorithm to find the longest paths from a single source.  The longest 
	 * path values (largest sums) are stored in <code>sums[]</code>.  
	 * <code>pred[]</code> can be used to trace the path from any vertex in the
     * graph back to the source.
     */
    private static void singleSourceLongestPath()
    {
        // Initialize the lists of maximum sums and predecessors
        sum = new int [vCount];
        pred = new int [vCount];
        for (int i=0; i < vCount; i++){
            sum[i] = 0;
            pred[i] = -1;
        }
        
        // The cost of starting at the source
        sum[0] = weights.get(0);
        
        // Iterate through all vertices in the graph.
        VertexIterator vitr = graph.new VertexIterator();
        while (vitr.hasNext())
        {
            Vertex u = vitr.next();

            // Iterate through the vertex's incident edges.
            EdgeIterator eitr = vitr.getEdgeIterator();
            while (eitr.hasNext())
            {
                WeightedEdge e = (WeightedEdge)eitr.next();
                Vertex v = e.vert;
                
                // Calculate the cost of the path
                int newSum = sum[u.getIdentifier()] + e.getWeight();
                
                // Does this path yield a higher sum?
                if (newSum > sum[v.getIdentifier()]){
                    sum[v.getIdentifier()] = newSum;
                    pred[v.getIdentifier()] = u.getIdentifier();
                }
            }
        }
    }
   
    /**
     * Searches the graph for the longest path (largest sum) from the source.
     * This is done by searching the <code>sum[]</code> array from right to left.
     * Only the vertices at the greatest depth need to be searched.
	 *
     * @return Index of the largest sum in <code>sum[]</code>
     */
    private static int findLargestSum()
    {
        int largest = -1;
        int index = -1;
        for (int i=0, pos = sum.length-1; i < height; i++, pos--){
            if (sum[pos] > largest){
                index = pos;
                largest = sum[index];
            }
        }
        return index;
    }
}
